package com.hy;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:1971. 寻找图中是否存在路径
 * <p>
 * 有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，
 * 其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连
 * 的边。
 * 请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
 * 给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，
 * 否则返回 false 。
 *
 * User:Mr.Du
 * Date:2024/4/17
 * Time:16:29
 */
public class ValidPath {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        QuickUnionUF uf = new QuickUnionUF(n);
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        return uf.connected(source, destination);
    }

    /**
     * 使用深度优先搜索（DFS）判断在给定的无向图中是否存在从源节点到目标节点的路径。
     * @param n 节点的总数。
     * @param edges 表示无向图中边的二维数组，每个边由两个节点索引组成。
     * @param source 源节点的索引。
     * @param destination 目标节点的索引。
     * @return 如果存在从源节点到目标节点的路径则返回true，否则返回false。
     */
    public boolean validPathDfs(int n, int[][] edges, int source, int destination){
        // 初始化节点邻接表
        List<Integer>[] list = new List[n];
        for(int i = 0;i < n;i++){
            list[i] = new ArrayList<>();
        }
        // 填充邻接表
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            list[x].add(y);
            list[y].add(x);
        }
        // 标记节点是否被访问
        boolean[] visited = new boolean[n];
        // 执行深度优先搜索并返回结果
        return dfs(list, visited, source, destination);
    }

    /**
     * 使用深度优先搜索（DFS）算法查找从源节点到目标节点的路径。
     * @param list 表示图的邻接表，list[i] 包含与节点 i 相邻的所有节点。
     * @param visited 记录每个节点是否被访问过的布尔数组。
     * @param source 源节点的索引。
     * @param destination 目标节点的索引。
     * @return 如果从源节点到目标节点存在路径，则返回 true；否则返回 false。
     */
    public boolean dfs(List<Integer>[] list, boolean[] visited, int source, int destination){
        // 当源节点等于目标节点时，表示已找到路径
        if(source == destination) return true;
        visited[source] = true; // 标记当前节点为已访问

        // 遍历当前节点的所有邻接节点
        for(int x : list[source]){
            // 如果邻接节点未被访问过，并且从该邻接节点到目标节点存在路径，则返回 true
            if(!visited[x] && dfs(list, visited, x, destination)){
                return true;
            }
        }
        return false; // 如果无法找到路径，则返回 false
    }

    /**
     * 使用广度优先搜索算法验证是否存在从源节点到目标节点的路径。
     *
     * @param n 节点的总数
     * @param edges 边的数组，每个元素为一个长度为2的数组，表示一条边连接的两个节点
     * @param source 源节点的编号
     * @param destination 目标节点的编号
     * @return 如果存在从源节点到目标节点的路径返回true，否则返回false
     */
    public boolean validPathBfs(int n, int[][] edges, int source, int destination) {
        // 初始化节点列表、队列和访问标记数组
        List<Integer>[] list = new List[n];
        Queue<Integer> queue = new ArrayDeque();
        boolean[] visited = new boolean[n];

        // 为每个节点初始化一个空的邻接节点列表
        for(int i = 0;i < n;i++){
            list[i] = new ArrayList<>();
        }

        // 根据边的数组构建邻接表
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            list[x].add(y);
            list[y].add(x);
        }

        // 将源节点入队，开始BFS
        queue.offer(source);
        while(!queue.isEmpty()){
            int x = queue.poll();
            // 如果节点已访问过，则跳过
            if(visited[x]) continue;
            // 如果找到目标节点，则返回true
            if(x == destination) return true;
            // 标记节点为已访问
            visited[x] = true;
            // 将未访问的邻接节点入队
            for(int y : list[x]){
                if(!visited[y]) queue.offer(y);
            }
        }

        // 如果队列为空还未找到目标节点，则返回false
        return false;
    }

}
